There are many applications where large volumes of digital data must be transmitted and/or stored and received and/or recovered substantially error free. For example, it is imperative that computer data base information, such as social security information, corporate sales and financial data, as well as satellite communications and research data, such as seismic or weather data, be transmitted and stored accurately.
Digital data is typically composed of binary units called "bits" with a group of bits (normally 8) making up a data "byte" or "symbol". Groups of bytes (normally 2) make up a data "word" or may alternatively be arranged into "blocks" of data (28 or 32 byte blocks are common). The errors that typically occur in the transmission, storage, reception and recovery of this data are of two types. The first type, termed a "random" or isolated error, occurs in a single bit when there is a substitution of one value, in a two value binary bit system, for its opposite value. The second type, termed a "burst" error, occurs when a continuous sequence of adjacent bits are in error. The length and frequency of burst type errors may be either random or systematic. In either case, the relative occurrence of these errors is generally a function of the media or channel employed.
Accurate transmission or storage and reception or recovery of digital data has historically been difficult because the media channels utilized for transmission or storage of data are plagued by error introducing factors. For example, such errors may be attributable to transient conditions in the storage device or transmission channel (noise, for example), or may be recurrent conditions resulting from defects in the channel, storage device or recording media. The existence of transient conditions or defects result in instances where the digital data is not transmitted or recorded properly or cannot be reliably received or recovered. Considerable attention has been directed toward discovering methods for reducing the transmission and storage errors that typically accompany data storage and transmission activities.
For example, it is well known in the art to employ error correction codes (ECCs) and other means to locate, counteract, correct and/or eliminate these errors. Such codes comprise additional or redundant bits periodically appended to discrete portions of the transmitted or stored data stream. The redundant bits are added to the discrete portion of the data stream to form code words. This well known process used to counter the occurrence of errors is commonly referred to as "encoding". Once encoded, the random errors in the transmitted or stored data stream are easily located and corrected by well known mathematical means. This process is commonly referred to as "decoding." Decoding typically involves utilizing the appended redundant bits as a parity check against the associated discrete portion of the data stream to detect and correct introduced errors.
Although many different error correction codes exist, the Reed-Solomon (R-S) code system is perhaps the most popular and commonly used symbol coding system. A "symbol" as used herein is comprised of m bits; with m being two or more bits and typically equal to eight bits in which case each symbol is equal to a data byte. An (N,K) R-S code is a code wherein K symbols of user data (data word or code group) have N-K error correction (parity check or code) symbols appended thereto to define a code word having a length of N symbols. The resulting N symbol code word can correct a minimum of T symbols of data error within the code word where T=(N-K)/2. For example, a (38,30) R-S code has a code word of 38 symbols in length and a data word (code group) of 30 symbols in length. Thus, there are eight parity check (code) symbols that enable a minimum of four errors to be corrected in each code word.
Decoders for R-S coded transmissions are well known in the art. These decoders process received code words and perform detection and correction processes on the data symbols according to the code symbols to output corrected code groups. Following correction, the parity check (code) symbols are stripped from the code word and the corrected data word (code group) is output. R-S codes can only correct T errors because it takes two code symbols to detect and correct one error. However, the R-S decoder also has the capability of showing within a known probability that the detection and correction capability of the decoder has been exceeded and that errors still exist in the output code group. Thus, the R-S decoders also include outputs that become active when the error correction capability of the decoder is exceeded.
The signals that appear at this additional decoder output are termed "erasure flags" where each flag is associated with a code word believed to still contain one or more errors. Typically, these erasure flags are used by subsequent decoders to assist in the correction of the flagged data in error. Erasure flags are beneficial because it requires only one code symbol to correct a flagged data error. Use of the erasure flags by subsequent decoders can thus enhance the correction capability of the decoder from a minimum of T to a maximum of 2T errors.
Furthermore, it is well known in the art to employ an interleaving process either before or after encoding to provide additional protection against included errors. Interleaving is a process performed on the transmitting or recording side of a system wherein consecutive bytes of digital information in the original data stream are separated from each other. Thus, bytes of digital information which were not adjacent prior to interleaving are concatenated and output as a new bit stream. Interleaving of data streams makes it less likely that consecutive bytes of digital information in the original stream will be adversely affected by a subsequent burst error as the burst error affects concatenated bytes from different portions of the original data stream. In the subsequent deinterleaving process, burst errors are effectively broken up and corrected in a piecemeal fashion by interleaving uncorrupted data from locations outside of the burst error into the bit stream.
The prior art discloses the use of both error correction coding and interleaving systems in combination to provide increased protection against random and burst errors encountered during data transmission and storage operations. For example, Deng, et al. describe a dual, interleaved error correction system in an article entitled Reliability and Throughput Analysis of a Concatenated Coding Scheme, published in IEEE Transactions on Communications, Vol. Com-35, No. 7, July 1987. In implementing the Deng, et al. system, encoding of the concatenated code is achieved in three steps. This three step process is figuratively shown in FIG. 1 of the article (reproduced herein as FIG. 1). First, a data message of a fixed number of bits is encoded into a code word by means of a first, outer encoding system. The code word is then interleaved, and after interleaving is encoded by a second, inner encoding system and output for transmission or storage by the media channel. Such an interleaved coding system has also been referred to as a cross-interleaved coding system and primarily used with an R-S code for the outer and inner coding systems. Systems such as that shown in FIG. 1 are well known in the art and commonly referred to by the acronym CIRC (Cross-Interleaved Reed-Solomon Code).
The use of multiple encoding steps and multiple interleaving steps, separately or in combination, to improve error detection and correction capability is disclosed by several published patents. For example, U.S. Pat. No. 3,786,439 issued to McDonald, et al. and Japanese patent No. 55-35562 are considered illustrative of simple triple encoding schemes. The patent issued to McDonald, et al., discloses a triple encoding scheme whereby a first encoder operates on segments of the data stream, a second encoder operates on groups of encoded segments and a third encoder operates on the encoded groups. In the Japanese patent, two error correction codes are appended onto a portion of the data stream, the dual encoded appended data stream further being encoded by a third encoder for appending of a third code and output. U.S. Pat. Nos. 4,730,321, issued to Machado, and 4,567,594, issued to Deodhar, are considered illustrative of simple triple interleaving schemes. Use of multiple encoding and interleaving steps provides improved detection and correction capability for encountered random and burst type errors.
Prior to outputting the encoded and/or interleaved data stream, it is well known in the art to use a media channel encoder on the data stream to counter the errors typically introduced by the use of certain transmission or recording media (for example, a digital tape recorder). The media channel encoding scheme is typically a run-length limiting code that protects against data sequencing errors. One such media channel encoding scheme known and widely used in the art is referred to as Miller-Squared encoding as described in U.S. Re. No. 31,311 issued to Miller. The conventional Miller-Squared decoder simply converts (decodes) the media channel encoded data stream for output.
The drawback associated with these prior art run-length limiting media channel decoders is that the decoded data stream is not checked for any errors introduced by the media channel. Thus, these unidentified errors are passed on to the subsequent decoding and deinterleaving steps. Because of the inherent limitations of the subsequent error correction decoders, the unidentified data errors introduced by the media channel may not be detected or even if detected, not corrected.
In summary, the more error correction code symbols added to the data, the more accurate the ability of the system to detect and correct included errors. However, the most significant drawback associated with multiple encoding schemes, such as the CIRC scheme, is that each encoding step adds redundant symbols to the data stream which occupy space that would otherwise be devoted to the user data. The current state of the art in error correction schemes does not present a scheme that accurately handles large volumes of digital data for transmission or storage while minimizing the number of included symbols devoted to error detection and correction.